/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
#include "iostream"

using namespace std;

struct ListNode {
    int val;
    ListNode *next;

    ListNode() : val(0), next(nullptr) {}

    ListNode(int x) : val(x), next(nullptr) {}

    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
private:
    int t[200001];
public:
    ListNode *sortList(ListNode *head) {
        memset(t, 0, 200001 * sizeof(int));
        ListNode *l = head, *h = head;
        while (l) {
            t[l->val + 100000]++;
            l = l->next;
        }
        for (int i = 0; i < 200001; ++i) {
            while (t[i]--) {
                h->val = i - 100000;
                h = h->next;
            }
        }
        return head;
    }
};